﻿// See https://aka.ms/new-console-template for more information
using System;

public enum NodeColor
{
    Red,
    Black
}

public class RedBlackNode<T> where T : IComparable<T>
{
    public T Value { get; set; }
    public NodeColor Color { get; set; }
    public RedBlackNode<T> Left { get; set; }
    public RedBlackNode<T> Right { get; set; }
    public RedBlackNode<T> Parent { get; set; }

    public RedBlackNode(T value, NodeColor color)
    {
        Value = value;
        Color = color;
        Left = null;
        Right = null;
        Parent = null;
    }
}

public class RedBlackTree<T> where T : IComparable<T>
{
    private RedBlackNode<T> root;
    private RedBlackNode<T> TNil;

    public RedBlackTree()
    {
        TNil = new RedBlackNode<T>(default(T), NodeColor.Black);
        root = TNil;
    }

    public void Insert(T value)
    {
        var newNode = new RedBlackNode<T>(value, NodeColor.Red)
        {
            Left = TNil,
            Right = TNil,
            Parent = null
        };

        RedBlackNode<T> y = null;
        RedBlackNode<T> x = root;

        while (x != TNil)
        {
            y = x;
            if (newNode.Value.CompareTo(x.Value) < 0)
            {
                x = x.Left;
            }
            else
            {
                x = x.Right;
            }
        }

        newNode.Parent = y;

        if (y == null)
        {
            root = newNode;
        }
        else if (newNode.Value.CompareTo(y.Value) < 0)
        {
            y.Left = newNode;
        }
        else
        {
            y.Right = newNode;
        }

        if (newNode.Parent == null)
        {
            newNode.Color = NodeColor.Black;
            return;
        }

        if (newNode.Parent.Parent == null)
        {
            return;
        }

        InsertFix(newNode);
    }

    private void InsertFix(RedBlackNode<T> k)
    {
        RedBlackNode<T> u;

        while (k.Parent.Color == NodeColor.Red)
        {
            if (k.Parent == k.Parent.Parent.Right)
            {
                u = k.Parent.Parent.Left;
                if (u.Color == NodeColor.Red)
                {
                    u.Color = NodeColor.Black;
                    k.Parent.Color = NodeColor.Black;
                    k.Parent.Parent.Color = NodeColor.Red;
                    k = k.Parent.Parent;
                }
                else
                {
                    if (k == k.Parent.Left)
                    {
                        k = k.Parent;
                        RightRotate(k);
                    }
                    k.Parent.Color = NodeColor.Black;
                    k.Parent.Parent.Color = NodeColor.Red;
                    LeftRotate(k.Parent.Parent);
                }
            }
            else
            {
                u = k.Parent.Parent.Right;

                if (u.Color == NodeColor.Red)
                {
                    u.Color = NodeColor.Black;
                    k.Parent.Color = NodeColor.Black;
                    k.Parent.Parent.Color = NodeColor.Red;
                    k = k.Parent.Parent;
                }
                else
                {
                    if (k == k.Parent.Right)
                    {
                        k = k.Parent;
                        LeftRotate(k);
                    }
                    k.Parent.Color = NodeColor.Black;
                    k.Parent.Parent.Color = NodeColor.Red;
                    RightRotate(k.Parent.Parent);
                }
            }
            if (k == root)
            {
                break;
            }
        }
        root.Color = NodeColor.Black;
    }

    private void LeftRotate(RedBlackNode<T> x)
    {
        var y = x.Right;
        x.Right = y.Left;
        if (y.Left != TNil)
        {
            y.Left.Parent = x;
        }
        y.Parent = x.Parent;
        if (x.Parent == null)
        {
            root = y;
        }
        else if (x == x.Parent.Left)
        {
            x.Parent.Left = y;
        }
        else
        {
            x.Parent.Right = y;
        }
        y.Left = x;
        x.Parent = y;
    }

    private void RightRotate(RedBlackNode<T> x)
    {
        var y = x.Left;
        x.Left = y.Right;
        if (y.Right != TNil)
        {
            y.Right.Parent = x;
        }
        y.Parent = x.Parent;
        if (x.Parent == null)
        {
            root = y;
        }
        else if (x == x.Parent.Right)
        {
            x.Parent.Right = y;
        }
        else
        {
            x.Parent.Left = y;
        }
        y.Right = x;
        x.Parent = y;
    }

    public void PrintTree()
    {
        if (root != TNil)
        {
            PrintTreeHelper(root, "", true);
        }
    }

    private void PrintTreeHelper(RedBlackNode<T> node, string indent, bool last)
    {
        if (node != TNil)
        {
            Console.Write(indent);
            if (last)
            {
                Console.Write("R----");
                indent += "     ";
            }
            else
            {
                Console.Write("L----");
                indent += "|    ";
            }

            string sColor = node.Color == NodeColor.Red ? "RED" : "BLACK";
            Console.WriteLine(node.Value + "(" + sColor + ")");
            PrintTreeHelper(node.Left, indent, false);
            PrintTreeHelper(node.Right, indent, true);
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        var rbTree = new RedBlackTree<int>();

        rbTree.Insert(55);
        rbTree.Insert(40);
        rbTree.Insert(65);
        rbTree.Insert(60);
        rbTree.Insert(75);
        rbTree.Insert(57);

        rbTree.PrintTree();
    }
}
